Searching for an arrangement of shapes that exactly or approximately satisfy one or more boundary distance (BD) constraints between those shapes make up a class of problems with many valuable commercial applications. For brevity we will refer to this as the boundary distance constrained arrangement (BDCA) problem. Instances of the BDCA problem include searching for arrangement of two or three dimensional components on or in a manufactured product such that no components overlap and all components are contained within the product's boundaries. Examples include, components inside the body of a car, components inside the case of a printer, rooms in a building, components on a circuit board or components on VLSI chip. Other instances include searching for an arrangement of one or more products or product components in or on a piece of material from which they are to be extracted such that there is sufficient space between them to allow for the kerf of the cutting tool while minimizing wasted material. Examples include the components of a pair of pants on a bolt of fabric or the components of a ship on a sheet of steel. Other instances outside of manufacturing and design include searching for an arrangement of packages inside a shipping container such that no packages occupy the same space and all packages fit inside the container. Some of these instances can further be extended into 4-dimensional problems where, for example, time constraints, or time dependent motion requirements are present.
In general, however, the BDCA problem is considered to be “computationally intractable”. That is, it may require an unreasonable amount of computing resources for the search to either find an arrangement that satisfies the BD constraints, or determine that no arrangement can satisfy the BD constraints. As such, for various classes of this problem, a great deal of effort has gone into developing an arsenal of methods which consume reasonable amounts of computing resources to search for arrangements that satisfy the BD constraints but which may not be able to find an arrangement that satisfies the BD constraints even if such an arrangement exists. For example, over the past 25 years, the electronics and VLSI circuit design industry have expended considerable effort on research and development for search methods that work on a limited subset of the two-dimensional version of the BDCA problem. In particular, they have been interested in the case where the shapes consist of axis-aligned (AA) rectangles. This is due to the fact that integrated circuit design at many levels of the physical design hierarchy are composed of collections of AA rectangles which must maintain specific physical relationships between the boundaries of the rectangles in the collection. Examples in this area include: the arrangement of AA rectangular mask shapes in the design of basic electronic components such as, for example, transistors, capacitors, and resistors; the arrangement of AA rectangular electronic components in the design of higher function circuits such as, for example, AND gates, OR gates, and Flip Flops (sometimes referred to as library cell design); the arrangement of AA rectangular circuits and AA rectangular electronic components in the design of macro blocks such as, for example, adders, multipliers, phase locked loops, and analog to digital converters (sometimes referred to as macro cell design); the arrangement of AA rectangular macros and AA rectangular circuits on a semiconductor substrates to design integrated circuit “chips”; the arrangement of AA rectangular IC “chips” to design multichip modules; and the arrangement of AA rectangular IC packages to design circuit boards.
Some of the oldest methods for dealing with BDCA problems approximate them as discrete combinatorial problems and then solve the approximations using either stochastic search methods, or problem specific deterministic heuristic search methods. This approach tends to require complex data structures to represent the search space of the BDCA problem and can only search a subset of the total search space of the original problem. Additionally, these data structures have limited ability to represent spatial relationships among the shapes. Demand for better coverage of the design space as well as an increase in the complexity of the spatial relationships has produced a steady stream of ever more complex data structures and methods for coping with these demands.
Analytical optimization provides another powerful tool that can be used to deal with BDCA problems. In particular, analytical optimization has the potential to provide a more general and flexible framework which is capable of representing the entire search space without the need for complex data structures, as well as the potential to handle complex special relationship among shapes. To date, however, there has been little progress in developing effective methods which make good use of the potential power and flexibility of analytical optimization methods when dealing with BDCA problems.
There are three interrelated obstacles that have limited the effective use of analytical optimization on BDCA problems: first, the need for an analytic representation of a BD constraint, or its approximation, between a pair of shapes; second, the need for an analytical representation of a BD constraint, or its approximation, that promotes efficient operation of an analytical optimizer on a BDCA problem; and third, the need for a method which can both improve the probability of an analytical optimizer finding an arrangement that satisfies the BD constraints and, when the BDCA problem contains an objective to be optimized, improving the probability of finding a high quality solution.